11113. Букет цветов для юниоров

Так как сегодня 8 марта, вы будете готовить букет цветов. В вашем магазине есть два вида цветов. Белые и красные цветы. Каждый букет должен состоять из 3-х цветов, и в букете должны быть оба вида цветов.

Если в вашем магазине имеется n белых и m красных цветов, какое максимальное количество букетов вы можете составить?

Вход. Два целых числа n и m (0 ≤ n, m ≤ 5 * 10⁵).

Выход. Выведите максимальное количество букетов, которые вы можете приготовить.

Пример входа	Пример выхода
88 100	62

РЕШЕНИЕ

математика

Анализ алгоритма

Пусть для определенности n ≤ m (в противном случае поменяем местами их значения). Если m ≥ 2n, то можно использовать все белые цветы, взяв в каждый букет по одному белому цветку. Максимальное число букетов равно n.

Пусть мы составили x букетов формата (б, б, к) и y букетов формата (б, к, к) (здесь б – белый, к – красный цветок). Тогда имеют место неравенства:

2x + y ≤ n,

x + 2y ≤ m

Сложив два неравенства и разделив на 3, получим:

x + y ≤ (n + m) / 3

То есть наибольшее количество букетов x + y всегда не больше (n + m) / 3.

Пример

Для заданного теста n = 88, m = 100. Количество букетов равно

(88 + 100) / 3 = 62

Реализация алгоритма

Читаем входные данные.

scanf("%d %d", &n, &m);

Если n > m, то поменяем местами их значения.

if (n > m)

{

temp = n; n = m; m = temp;

}

Выводим ответ.

if (m >= n * 2)

printf("%d\n", n);

else

printf("%d\n", (n + m) / 3);